/************************************************************************

								Heroes IV
					  Copyright 2001, The 3DO Company

	------------------------------------------------------------------
  						 combat_ai_melee_action.h

	$Header: $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "combat_ai_melee_action.h"

#include <limits>
#include <math.h>
#include <queue>
#include <sstream>
#include <utility>
#include <vector>
#include "angle.h"
#include "attack_angle.h"
#include "battlefield.h"
#include "can_cast.h"
#include "castle_gate.h"
#include "circle_calculator.h"
#include "combat_ai.h"
#include "combat_ai_defend_action.h"
#include "combat_ai_move_action.h"
#include "combat_creature_ai_data.h"
#include "combat_creature_list.h"
#include "combat_creature.h"
#include "combat_footprint.h"
#include "difficulty_level.h"
#include "elements_of.h"
#include "random.h"
#include "town_image_level.h"

// -----------------------------------------------------------
// determine if a give point contains an attackable obstacle
// returns null if we own all obstacles, or if an obstacle is 
// a creature.
// -----------------------------------------------------------
static t_abstract_combat_object* get_attackable_obstacle( t_combat_creature const&  creature, 
														  t_map_point_2d const&		cell_point )
{
	t_battlefield&				battlefield = creature.get_battlefield();
	t_combat_footprint const&	footprint = creature.get_footprint();
	int							footprint_size = footprint.get_size();
	t_map_point_2d				offset;
	t_map_point_2d				new_point;
	int const*					ptr = footprint.get();
	t_abstract_combat_object*	object;
	t_abstract_combat_object*	result = 0;
	
	for (offset.row = 0; offset.row < footprint_size; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size; offset.column++)
		{
			if (!(*(ptr++)))
				continue;
			new_point = cell_point + offset;
			object = battlefield.get_cell( new_point ).get_attackable_object();
			if (object == 0)
				continue;
			// don't try and smash anything we own, like a castle gate.
			if (object->get_attackable_object()->belongs_to( creature.get_controller() ))
				continue;
			// if we encounter a creature, stop.  We're looking for stuff we can break.
			if (dynamic_cast<t_combat_creature*>(object) != 0)
				continue;
			result = object;
		}
	}
	return result;
}


// -----------------------------------------------------------
// find an alternate route to the target that assumes friendlies will move
// -----------------------------------------------------------
static int get_alternate_move_time( t_combat_creature const&	creature, 
									t_map_point_2d const&		destination,
									t_combat_object_ptr&		object,
									t_map_point_2d&				waypoint )
{
	if (creature.get_cell_position() == destination)
		return 1;

	int							movement = creature.get_combat_movement();
	t_combat_path_finder&		path_finder = creature.get_path_finder( false );
	t_combat_path_finder&		alternate_path_finder = creature.get_path_finder( true );
	t_combat_path				path;

	alternate_path_finder.get_path( destination, path );

	// search for the first point where the alternate path diverges from the
	// primary pathfinder
	int							i;
	t_combat_path_data const*	path_point;

	for (i = 0; i < path.size(); ++i)
	{
		path_point = &path_finder.get_data( path[i] );
		if (path_point->visited && path_point->move_cost <= path[i].move_cost 
			&& !path_point->blocked)
			break;
	}
	if (i == 0)
	{
		waypoint = path[0];
		return (path[0].move_cost + movement - 1) / movement;
	}

	t_battlefield&	battlefield = creature.get_battlefield();

	int alternate_turns;

	if (i == path.size())
	{
		waypoint = creature.get_cell_position();
		alternate_turns = (path[0].move_cost + movement - 1) / movement + 1;
	}
	else
	{
		int distance;

		waypoint = path[i];
		distance = path[0].move_cost - path[i].move_cost;
		assert( distance > 0 );
		alternate_turns = (distance + movement - 1) / movement;
		distance = path[i].move_cost;
		assert( distance > 0 );
		alternate_turns += (distance + movement - 1) / movement;
	}

	// check if there's a rock / gate we must attack
	while (i--)
	{
		object = get_attackable_obstacle( creature, path[i] );
		if (object != 0)
		{
			t_attackable_object* obstacle = object->get_attackable_object();
			int					 damage;
		
			damage = creature.get_melee_damage( *obstacle, 0 ) * creature.get_attacks( false );
			alternate_turns += (obstacle->get_total_hits() - 1) / damage;
			if (alternate_turns > 9)
				alternate_turns = 9;
			break;
		}
	}
	return alternate_turns;
}

// ---------------------------------------------------------------------------------------
// constructor
// ---------------------------------------------------------------------------------------
t_combat_ai_melee_action::t_combat_ai_melee_action( t_battlefield&			battlefield,
												    t_combat_creature_ptr	target, 
													t_attack_angle const&	attack_angle,
													bool					unreachable )
						: t_abstract_combat_ai_action( battlefield ), m_target(target), 
						  m_attack_angle(attack_angle), 
						  m_unreachable(unreachable)
{
	t_combat_creature*	creature = battlefield.get_acting_creature();
	int					movement = creature->get_combat_movement();

	m_blocked = m_unreachable;
	m_destination = attack_angle.point;
	if (unreachable)
	{ // consider alternate routes
		t_ai_combat_data_cache&		data = battlefield.get_data_cache();
		t_attack_angle_list const&	attack_angles = data.get_attack_angles( *creature, *m_target,
																			true );
		m_turns = 10;
		if (attack_angles.empty())
		{
			m_attack_angle.point = creature->get_cell_position();
			m_attack_angle.attack_angle = get_angle( m_attack_angle.point, 
													 creature->get_cell_position() );
			m_attack_angle.attack_distance = 0;
			m_attack_angle.move_distance = 10 * creature->get_combat_movement();
		}
		else
		{
			m_unreachable = false;
			m_blocked = true;
			m_attack_angle = *attack_angles.get_closest();
			m_turns = get_alternate_move_time( *creature, m_attack_angle.point, m_obstacle,
											   m_destination );
		}
	}
	else
	{
		int alternate_turns;

		m_turns = (attack_angle.move_distance + movement - 1) / movement;
		if (m_turns < 1)
			m_turns = 1;
		if (m_turns > 2)
		{
			t_combat_object_ptr obstacle;
			t_map_point_2d		destination;

			alternate_turns = get_alternate_move_time( *creature, m_attack_angle.point, obstacle,
													   destination );
			if (m_turns > alternate_turns)
			{
				m_turns = alternate_turns;
				m_blocked = true;
				m_obstacle = obstacle;
				m_destination = destination;
			}
		}
	}
}


// Normal weighting of actions
void t_combat_ai_melee_action::weigh_action(t_combat_ai const& owner)
{
	if (has_been_weighed())
		return;

	t_combat_creature const& attacker = owner.get_actor();

	// Attacking in a future turn.
	bool retaliate = m_target->can_retaliate( attacker, false, m_turns )
		 && m_battlefield.get_difficulty() >= k_difficulty_normal;

	set_weight( get_action_weight(owner, retaliate ) );
}

// --------------------------------------------------------------------
// determine if compute total value of removing an object from its current position
// --------------------------------------------------------------------
static bool contains_other_members( t_combat_creature_list const& list, 
								    t_combat_creature const* creature )
{
	t_combat_creature_list::const_iterator index = list.begin();
	t_combat_creature_list::const_iterator end = list.end();

	for (; index != end; ++index )
	{
		if (index->get() != creature)
			return true;
	}
	return false;
}

// --------------------------------------------------------------------
// compute total value of removing an object from its current position
// --------------------------------------------------------------------
static double get_zoc_removal_value( t_combat_creature const& target )
{
	t_battlefield &battlefield = target.get_battlefield();

	// Weight from removing interference with friendly units
	double weight = 0.0;
	int target_hps = target.get_total_hits();

	assert(target_hps > 0);

	t_ai_combat_data_cache&					data = battlefield.get_data_cache();
	t_combat_creature_list const&			target_interferes_with_list
		= data.get_creature_interferes_with_list(target);
	t_combat_creature_list::const_iterator	inteferee_iterator;

	for (inteferee_iterator = target_interferes_with_list.begin(); 
		 inteferee_iterator != target_interferes_with_list.end(); ++inteferee_iterator )
	{
		t_combat_creature const& interferee = **inteferee_iterator;

		// Add in remaining interferers
		t_combat_creature_list const& interfered_by_list 
			= data.get_interferes_with_creature_list(interferee);

		if (!contains_other_members( interfered_by_list, &target ))
			weight += interferee.get_interference_bonus();
	}

	double penalty = target.get_interference_bonus();

	if (penalty > 0.0 && !data.get_interferes_with_creature_list( target ).empty() )
		weight -= penalty;

	return weight;
}

// --------------------------------------------------------------------
// compute total value of adding to its current position
// --------------------------------------------------------------------
static double get_zoc_add_value( t_battlefield&					battlefield,
								 t_combat_creature_list const&	list, 
								 t_combat_creature const*		creature )
{
	t_combat_creature_list::const_iterator	index = list.begin();
	t_combat_creature_list::const_iterator	end = list.end();
	t_ai_combat_data_cache&					data = battlefield.get_data_cache();
	double									result = 0.0;

	for (; index != end; ++index)
	{
		t_combat_creature const&		target = **index;
		t_combat_creature_list const&	interfered_by = 
			data.get_interferes_with_creature_list( target );
		
		if (!contains_other_members( interfered_by, creature ))
			result += target.get_interference_bonus();
	}
	return result;
}

/*
zone of control change:
	remove penalty to attacker for being interefered with
	remove attacker's bonuses for intefering in old location
	remove target's bonuses for interfering in old position, angle
	remove target's penalty for being interferred

	generate attacker's new interference list
	generate target's new interference list.  Include attacker.

	add penalty to attacker for being inteferred with
	add attacker's bonuses for interfering in new location
	add target's bonuses for interfering in new position, angle.  Exclude attacker.

	get value of reducing target, based on target's updated interference list
	get value of reducing attacker, based on future interference list
*/
static double get_zoc_change( t_combat_creature const&	attacker,
							  t_combat_creature const&	target,
							  t_attack_angle const&		attack_angle,
							  t_creature_int_map&		damage_map,
							  bool						retaliate )
{
	t_battlefield&			battlefield = attacker.get_battlefield();
	t_ai_combat_data_cache& data = battlefield.get_data_cache();
	double					result = 0.0;
	double					attacker_value = attacker.get_interference_bonus();

	// remove all old benefits of attacker and target location
	result -= get_zoc_removal_value( attacker );
	// exclude attacker from value of target's interference
	result += get_zoc_removal_value( target );
	// if the target interferes with the attacker, it's been counted twice above,
	// so subtract one copy.
	if (attacker_value > 0.0 && target.interferes( attacker ))
		result -= attacker_value;

	// compute ending angles
	t_direction attacker_direction;
	t_direction	target_direction;

	attacker_direction = get_direction( attack_angle.attack_angle );
	attacker_direction = attacker.get_wait_direction( attacker_direction, attack_angle.point );
	if (retaliate)
	{
		int			target_angle;

		target_angle = (attack_angle.attack_angle + 180) % 360;
		target_direction = get_direction( target_angle );
		target_direction = target.get_wait_direction( target_direction );
	}
	else
	{
		// target will not change direction
		target_direction = target.get_current_direction();
	}

	// compute value added by interfering.
	t_combat_creature_list	list;

	if (damage_map[&attacker] < attacker.get_total_hits())
	{
		attacker.get_interfere_with_list( list, attack_angle.point, attacker_direction );
		result += get_zoc_add_value( battlefield, list, &attacker );
	}
	else
	{
		double target_value = target.get_interference_bonus();

		if (target_value > 0.0)
		{
			// check if target is still interfered by creatures other than attacker
			data.get_interferes_with_creature_list( target );
			if (contains_other_members( list, &attacker ))
				result += target_value;
		}
	}

	int damage = damage_map[&target];

	list.clear();
	if (damage < target.get_total_hits())
	{
		target.get_interfere_with_list( list, target.get_cell_position(), target_direction );
		result -= get_zoc_add_value( battlefield, list, &target );
	}
	
	// check if we did not adjust above for the attacker moving into enemy ZOC's.
	if ( attacker_value > 0.0 )
	{
		t_combat_creature_list::iterator index = list.begin();
		t_combat_creature_list::iterator end = list.end();

		// check if we included it when counting the target's ZOC value
		for (; index != end; ++index)
		{
			if (index->get() == &attacker)
				break;
		}
		if (index == end)
		{
			// assume that the target interferes if it wasn't killed
			if (retaliate && damage < target.get_total_hits())
				result -= attacker_value;
			else
			{
				// check if something else inteferes here
				attacker.get_interfered_by_list( list, attack_angle.point );
				// we assume that if we've reached here, the target does not intefere,
				// either because of facing or because it's destroyed.
				if ( contains_other_members( list, &target ) )
					result -= attacker_value;
			}
		}
	}
	return result;
}	  


double t_combat_ai_melee_action::get_action_weight( t_combat_ai const& owner,
												    bool retaliate)
{
	t_combat_creature const&	attacker = owner.get_actor();
	t_battlefield&				battlefield = attacker.get_battlefield();

	// Determine retaliation effects 

	int attack_distance = m_attack_angle.move_distance;
	int combat_movement = attacker.get_combat_movement();

	if (attack_distance > combat_movement || m_unreachable)
	{
		attack_distance = combat_movement;
	}

	t_creature_int_map damage_map;

	attacker.get_melee_exchange_effect( *m_target, attack_distance, damage_map, m_attack_angle, 
										m_target->get_cell_position(), retaliate );

	double					weight = get_total_weight( damage_map, attacker.get_controller() );
	t_ai_combat_data_cache& data = battlefield.get_data_cache();

	bool dies_along_way = data.get_approximate_lifespan( attacker ) < m_turns;
	
	if (!m_unreachable)
	{
		double zoc_change;

		zoc_change = get_zoc_change( attacker, *m_target, m_attack_angle, damage_map, retaliate );
		zoc_change += data.get_influence_weight( m_attack_angle.point );

		if (!dies_along_way || zoc_change < 0)
			weight += zoc_change;
	}

	int retal_damage = damage_map[&attacker];

	if (retal_damage > 0)
	{
		double retaliation_weight;
		double reduction;

		// retaliation weight has already been included.  We're just seeing if we should limit it.
		retaliation_weight = attacker.get_ai_value( retal_damage );
		reduction = data.get_retaliation_weight_reduction( *m_target, false );
		if (retaliation_weight > reduction)
		{
			weight += reduction;
		}
		else
		{
			weight += retaliation_weight;
		}
	}
	if (dies_along_way && weight > -m_turns)
		weight = -m_turns;

	// Penalty for far-away units
	if (weight > 0.0)
		weight = weight / m_turns;
	return weight;
}

// -----------------------------------------------------------
// attack or move
// -----------------------------------------------------------
static void attack( t_battlefield& battlefield, t_abstract_combat_object* target, 
				    t_attack_angle const& attack_angle )
{
	if (attack_angle.move_distance > battlefield.get_acting_creature()->get_combat_movement())
		t_combat_ai_move_action::perform_move( battlefield, attack_angle.point );
	else
		battlefield.move_to_attack( target, attack_angle.point );
}

// -----------------------------------------------------------
// attack an obstacle
// -----------------------------------------------------------
static bool attack_obstacle( t_combat_creature const&	attacker,
							 t_abstract_combat_object&	object )
{
	t_battlefield&				battlefield = attacker.get_battlefield();
	t_ai_combat_data_cache&		data = battlefield.get_data_cache();
	t_attackable_object const&	target = *object.get_attackable_object();
	t_attack_angle_list const&	attack_angles = data.get_attack_angles( attacker, target,
																		false );
	t_attack_angle const*		attack_angle;
	
	if (attacker.has_ability( k_ability_charging ))
		attack_angle = attack_angles.get_farthest();
	else
		attack_angle = attack_angles.get_closest();
	
	if (attack_angle == 0)
		return false;
	attack( battlefield, &object, *attack_angle );
	return true;
}

// -----------------------------------------------------------
// get value of destroying a castle gate
// -----------------------------------------------------------
static double gate_destruction_value( t_battlefield& battlefield, bool side )
{
	double								wall_bonus = battlefield.get_castle_wall_bonus();
	t_combat_creature_list::iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	end = battlefield.creatures_end();
	t_combat_creature*					creature;
	double								walker_value = 0.0;
	double								total_value = 0.0;
	double								result = 0.0;

	for (; index != end; ++index)
	{
		creature = *index;
		if (creature->get_number() == 0)
			continue;
		if (creature->get_controller() == side)
		{
			double value = creature->get_combat_value();

			if (creature->get_ai_melee_value_per_hit() > creature->get_ai_ranged_value_per_hit()
				&& creature->get_ai_melee_value_per_hit() > creature->get_ai_spellcasting_value_per_hit())
				walker_value += value;
			total_value += value;
			continue;
		}

		double defense_value = creature->get_defense_decrease_ai_value( wall_bonus - 1.0, false );
		double damage = (creature->get_damage_low() + creature->get_damage_high()) * 0.5;
		double damage_change = damage - damage / wall_bonus;
		double attack_value = creature->get_damage_decrease_ai_value( damage_change, false );

		result += defense_value + attack_value;
	}
	if (walker_value == 0.0)
		return 0.0;
	return result * walker_value / total_value;
}


// -----------------------------------------------------------
// consider attacking the gate instead
// -----------------------------------------------------------
static bool attack_gate( t_combat_creature const&	attacker,
						 t_combat_creature const&	defender,
						 t_attack_angle const&		attack_angle,
						 double						attack_weight )
{
	t_battlefield& battlefield = attacker.get_battlefield();

	if (battlefield.gate_is_open())
		return false;
	if (attacker.has_ability( k_ability_flying ))
		return false;

	t_map_point_2d	attacker_center = attacker.get_footprint_center( attack_angle.point );
	t_map_point_2d	defender_center = defender.get_footprint_center();
	t_wall_bonus	wall_bonus = battlefield.crosses_wall( attacker_center, defender_center );

	if (wall_bonus != k_wall_bonus_defense)
		return false;

	t_castle_gate*	gate = battlefield.get_gate();
	int				damage_low	= attacker.get_damage_low();
	int				damage_high	= attacker.get_damage_high();
	int				damage		= (damage_low + damage_high) * attacker.get_number() / 2;
	int				gate_hits = gate->get_total_hits();
	double			weight;

	damage = attacker.adjust_attack_damage( damage, *gate, false, 0, k_wall_bonus_none );
	if (damage > gate_hits)
		damage = gate_hits;
	
	weight = gate_destruction_value( battlefield, attacker.get_controller() ) 
			 * damage / gate_hits;
	if (weight <= attack_weight)
		return false;

	return attack_obstacle( attacker, *gate->get_object() );
}

// -----------------------------------------------------------
// nudge creatures along path so they don't wait
// -----------------------------------------------------------
static void mark_path_cell( t_isometric_map<int>&		map, 
						    t_combat_creature const&	creature, 
					        t_map_point_2d const&		cell_point )
{
	t_battlefield&				battlefield = creature.get_battlefield();
	t_combat_footprint const&	footprint = creature.get_footprint();
	int							footprint_size = footprint.get_size();
	t_map_point_2d				offset;
	t_map_point_2d				new_point;
	int const*					ptr = footprint.get();
	
	for (offset.row = 0; offset.row < footprint_size; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size; offset.column++)
		{
			if (!(*(ptr++)))
				continue;
			new_point = cell_point + offset;
			map.get( new_point ) = true;
		}
	}
}

// -----------------------------------------------------------
// mark squares that are along path 
// -----------------------------------------------------------
static void mark_path_area( t_isometric_map<int>& map, t_combat_creature const& creature,
						    t_map_point_2d const& destination )
{
	t_combat_path_finder&   path_finder = creature.get_path_finder( true );
	t_combat_path			path;
	int						i;

	if (!path_finder.get_path( destination, path ))
		return;

	for (i = 0; i < path.size(); ++i)
		mark_path_cell( map, creature, path[i] );
}

// -----------------------------------------------------------
// mark all paths that block other creatures
// -----------------------------------------------------------
static bool mark_all_paths( t_isometric_map<int>&		map, 
						    t_combat_creature const&	current_creature )
{
	t_battlefield& battlefield = current_creature.get_battlefield();
	t_combat_creature_list::iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	end = battlefield.creatures_end();
	bool								side = current_creature.get_controller();
	t_combat_creature const*			creature;
	t_combat_ai_melee_action const*		action;
	bool								any_marked = false;

	for (; index != end; ++index)
	{
		creature = *index;
		if (creature->get_number() == 0)
			continue;
		if (creature->get_controller() != side)
			continue;
		if (creature == &current_creature)
			continue;
		action = creature->get_melee_action();
		if (action == 0)
			continue;
		
		t_map_point_2d destination = action->get_attack_angle().point;

		any_marked = true;
		mark_path_area( map, *creature, destination );
	}
	return any_marked;
}

// -----------------------------------------------------------
// check if cell contains a blocked path
// -----------------------------------------------------------
static bool contains_path( t_isometric_map<int>& map, t_combat_creature const& creature,
						   t_map_point_2d const& position )
{
	t_map_point_2d				offset;
	t_map_point_2d				point;
	t_combat_footprint const&	footprint = creature.get_footprint();
	int							footprint_size = footprint.get_size();
	int const*					ptr = footprint.get();

	for (offset.row = 0; offset.row < footprint_size; ++offset.row)
	{
		for (offset.column = 0; offset.column < footprint_size; ++offset.column)
		{
			if (!(*(ptr++)))
				continue;
			point = position + offset;
			if (map.get( point ))
				return true;
		}
	}
	return false;
}

// -----------------------------------------------------------
// check if it's worth moving away to unblock cells
// -----------------------------------------------------------
static bool unblock_paths( t_combat_creature&	creature )
{
	t_battlefield&			battlefield = creature.get_battlefield();
	t_isometric_map<int>	map( battlefield.get_size(), k_battlefield_cell_height,
							     k_battlefield_logical_view_size, 0 );
	t_map_point_2d			position = creature.get_cell_position();

	if (!mark_all_paths( map, creature ))
		return false;
	if (!contains_path( map, creature, position))
		return false;

	t_map_point_2d				point;
	t_map_point_2d				delta;
	t_map_point_2d				closest_point;
	int							distance;
	int							closest_distance;
	bool						found = false;
	t_combat_path_finder&		path_finder = creature.get_path_finder();
	int							size = path_finder.get_size();
	int							row_end;
	t_combat_path_data const*	path_data;

	for (point.row = 0; point.row < size; ++point.row)
	{
		point.column = path_finder.get_row_start( point.row );
		row_end = path_finder.get_row_end( point.row );
		for (; point.column < row_end; ++point.column)
		{
			path_data = &path_finder.get_data( point );
			if (!path_data->visited)
				continue;
			if (path_data->blocked)
				continue;
			delta = point - position;
			distance = delta.row * delta.row + delta.column * delta.column;
			if (found && distance >= closest_distance)
				continue;
			if (contains_path( map, creature, point ))
				continue;
			found = true;
			closest_distance = distance;
			closest_point = point;
		}
	}
	if (!found)
		return false;
	t_combat_ai_move_action::perform_move( battlefield, closest_point );
	return true;
}

// -----------------------------------------------------------
// nudge creatures along path so they don't wait
// -----------------------------------------------------------
static void nudge_creatures( t_combat_creature const&  creature, 
						     t_map_point_2d const&		cell_point )
{
	t_battlefield&				battlefield = creature.get_battlefield();
	t_combat_footprint const&	footprint = creature.get_footprint();
	int							footprint_size = footprint.get_size();
	t_map_point_2d				offset;
	t_map_point_2d				new_point;
	int const*					ptr = footprint.get();
	t_abstract_combat_object*	object;
	t_combat_creature*			target;
	
	for (offset.row = 0; offset.row < footprint_size; offset.row++)
	{
		for (offset.column = 0; offset.column < footprint_size; offset.column++)
		{
			if (!(*(ptr++)))
				continue;
			new_point = cell_point + offset;
			object = battlefield.get_cell( new_point ).get_attackable_object();
			if (object == 0)
				continue;
			target = dynamic_cast<t_combat_creature*>( object );
			if (target == 0)
				continue;
			if (target == &creature)
				continue;
			if (target->get_controller() != creature.get_controller())
				continue;
			if (target->is_waiting() || target->has_moved())
				continue;
			target->get_ai_data().do_not_wait = true;
		}
	}
}

// -----------------------------------------------------------
// nudge creatures along path so they don't wait
// -----------------------------------------------------------
static void nudge_creatures_on_path( t_combat_creature const&	creature, 
									 t_map_point_2d const&		destination )
{
	t_combat_path_finder&   path_finder = creature.get_path_finder( true );
	t_combat_path			path;
	int						i;

	if (!path_finder.get_path( destination, path ))
		return;

	for (i = 0; i < path.size(); ++i)
		nudge_creatures( creature, path[i] );
}


// -----------------------------------------------------------
void t_combat_ai_melee_action::perform_action(void)
{
	t_battlefield&			battlefield = m_battlefield;
	t_combat_creature*		creature = battlefield.get_acting_creature();
	// try pathfinding ignoring friendly creatures...
	
	assert(t_circle_calculator::k_max_offset == battlefield.get_size());

	if (!creature->is_waiting() && !creature->get_ai_data().do_not_wait
		&& !creature->has_ability( k_ability_berserk )
		&& battlefield.get_difficulty() >= k_difficulty_hard )
	{
		if (m_unreachable || m_turns > 1 || !threatens_enemies( *m_target ))
		{
			if (m_blocked && !m_unreachable)
			{
				nudge_creatures_on_path( *creature, m_attack_angle.point );
				creature->set_melee_action( this );
			}
			battlefield.wait_action();
			return;
		}
	}
	if (m_unreachable || m_blocked)
	{
		if (unblock_paths( *creature ))
			return;
	}

	if (!m_unreachable)
	{
		if (m_blocked)
		{
			if (m_obstacle != 0 && attack_obstacle( *creature, *m_obstacle ))
				return;
			if (m_destination == creature->get_cell_position())
			{
				creature->set_melee_action( this );
				nudge_creatures_on_path( *creature, m_attack_angle.point );
				battlefield.defend();
				return;
			}
			t_combat_ai_move_action::perform_move( battlefield, m_destination );
			return;
		}
		if (attack_gate( *creature, *m_target, m_attack_angle, m_basic_weight ))
			return;
		attack( battlefield, m_target, m_attack_angle );
		return;
	}

	// Just can't get there! Fall back to geometricly closest reachable point
	t_combat_path_finder&	path_finder = creature->get_path_finder( false );
	t_circle_calculator		circle(m_target->get_cell_position());
	t_map_point_2d			point;

	while (circle.get_next_point(point))
	{
		if (   point.column >= 0 
			&& point.column < battlefield.get_size() 
			&& battlefield.is_valid(point))
		{
			const t_combat_path_data &point_data = path_finder.get_data(point);

			if (point_data.visited && !point_data.blocked)
			{
				// Move to point
				t_combat_ai_move_action::perform_move(battlefield, point);
				return;
			}
		}
	}
	
	// Sigh -- nothing working, just defend
	battlefield.defend();
}

namespace
{
	// Extension of t_attack_angle which includes the damage done
	// at that angle
	struct t_attack_angle_with_damage : public t_attack_angle
	{
		int damage;
		bool backstab;
		
		// Convenience constructor
		t_attack_angle_with_damage(const t_attack_angle &attack_angle, int dam, bool backstab_val);
	};

	inline
	t_attack_angle_with_damage::t_attack_angle_with_damage(const t_attack_angle &attack_angle, int dam, bool backstab_val)
		: t_attack_angle(attack_angle), damage(dam), backstab(backstab_val)
	{
	}

	typedef std::list<t_attack_angle_with_damage> t_angle_damage_list;

}

//--------------------------------------------------------------------
// Predicate for sorting t_angle_damage_list; puts all angles with
// same damage together, with the closest one first
// Operator() returns true if angle1 > angle2
// (Brain-dead non-standard implementation makes us do this with
// template specialization)
//--------------------------------------------------------------------
template<> struct std::greater<t_attack_angle_with_damage> : public binary_function<t_attack_angle_with_damage, t_attack_angle_with_damage, bool> 
{
	bool operator()(const t_attack_angle_with_damage& x, const t_attack_angle_with_damage& y) const;
};

inline
bool std::greater<t_attack_angle_with_damage>::operator()(const t_attack_angle_with_damage& x, const t_attack_angle_with_damage& y) const
{
	if (x.damage < y.damage)
		return false;

	if (x.damage > y.damage)
		return true;

	return x.move_distance < y.move_distance;
}

//--------------------------------------------------------------------
// get adjusted movement time
//--------------------------------------------------------------------
static int get_move_time( int distance, t_combat_creature const& actor )
{
	int move_time = ((distance - 1) / actor.get_combat_movement()) + 1;

	if (move_time < 1)
		move_time = 1;

	if (move_time < 2 && actor.is_active(k_spell_song_of_peace))
		move_time = 2; // Can't attack this turn anyway
	return move_time;
}


//--------------------------------------------------------------------
// Generate all legitimate melee actions for a given target
//--------------------------------------------------------------------
static 
t_combat_ai_melee_action_ptr generate_melee_action( t_combat_creature*	target, 
													t_combat_ai const&	combat_ai,
													bool				stay_inside_castle )
{
	t_combat_creature const& actor = combat_ai.get_actor();
	t_attack_angle			 attack_angle;
	t_attack_angle_list		 attack_angles;
	t_battlefield&			 battlefield = actor.get_battlefield();

	battlefield.get_attack_angles( actor, *target, attack_angles);
	if (attack_angles.empty())
	{
		// Generate an "unreachable" melee attack
		if (stay_inside_castle && !battlefield.is_in_castle( target->get_cell_position() ))
			return 0;
		return new t_combat_ai_melee_action(battlefield, target, attack_angle, true);
	}

	int move_time;

	attack_angle = *(attack_angles.get_closest());
	move_time = get_move_time( attack_angle.move_distance, actor );

	if (stay_inside_castle && !battlefield.is_in_castle( attack_angle.point ))
		return 0;

	if (move_time > 1)
	{
		return new t_combat_ai_melee_action( battlefield, target, attack_angle, false );
	}

	// Possibly generate multiple actions for close units if the different
	// points would generate different damages (Either because of backstab
	// or charging, or area effect)
	// Throw away anything that would require more than 1 turn of 
	// movement. Turn remaining t_attack_angle's into 
	// t_attack_angle_with_damage's.
	int							 max_move_distance = actor.get_combat_movement(); // Throw away above this
	t_combat_ai_melee_action_ptr best_action;
	t_combat_ai_melee_action_ptr action;

	t_attack_angle_list::iterator angle;

	for (angle = attack_angles.begin(); angle != attack_angles.end(); angle++)
	{
		if (angle->move_distance > max_move_distance)
			continue;

		action = new t_combat_ai_melee_action( battlefield, target, *angle, false );
		if (best_action == 0
			|| action->get_weight( combat_ai ) > best_action->get_weight( combat_ai ))
			best_action = action;
	}
	return best_action;
}


//--------------------------------------------------------------------
// compare two melee actions
// is the left action less valuable than the right action?
//--------------------------------------------------------------------
bool less_than( t_combat_ai_melee_action& left,
			    t_combat_ai_melee_action& right,
				t_combat_ai const&		  combat_ai )
{
	// melees that are not reachable are worth less than
	// melees we can reach
	if (left.get_unreachable())
	{
		if (!right.get_unreachable())
			return true;
	}
	else
	{
		if (right.get_unreachable())
			return false;

		// if we can reach both, we can determine the time to target
		int left_time = left.get_turns();
		int right_time = right.get_turns();

		// multi-turn melees are worth less than single turn melees
		if (left_time > 1)
		{
			if (right_time <= 1)
				return true;
		}
		else
		{
			if (right_time > 1)
				return false;
		}
	}
	return (left.get_weight( combat_ai ) < right.get_weight( combat_ai ));
}

//--------------------------------------------------------------------
// check if side has any creatures outside the castle
//--------------------------------------------------------------------
static bool has_creatures_outside_castle( t_battlefield& battlefield, bool side )
{
	if (battlefield.get_castle_level() == k_town_image_village)
		return true;

	t_combat_creature_list::iterator	index = battlefield.creatures_begin();
	t_combat_creature_list::iterator	end = battlefield.creatures_end();
	t_combat_creature*					creature;

	for (; index != end; ++index)
	{
		creature = *index;
		if (creature->get_number() == 0)
			continue;
		if (creature->belongs_to_defender() != side)
			continue;
		if (!battlefield.is_in_castle( creature->get_cell_position() ))
			return true;
	}
	return false;
}

//--------------------------------------------------------------------
// Generate all legitimate melee actions
//--------------------------------------------------------------------
t_combat_ai_action_ptr generate_best_melee_action( t_combat_ai&	combat_ai )
{
	t_combat_creature&					attacker = combat_ai.get_actor();
	t_battlefield&						battlefield = attacker.get_battlefield();
	t_ai_combat_data_cache&				data = battlefield.get_data_cache();
	bool								side = attacker.get_controller();
	t_combat_creature_list::iterator	creature_iterator;
	t_combat_ai_melee_action_ptr		action;
	t_combat_ai_melee_action_ptr		best_action;
	bool								creatures_outside_castle;
	bool								is_poisoned;
	bool								stay_in_castle;

	creatures_outside_castle = has_creatures_outside_castle( battlefield, side )
							|| battlefield.gate_is_open();
	is_poisoned = attacker.is_active( k_spell_poison ) || attacker.is_active( k_spell_plague );
	stay_in_castle = !creatures_outside_castle && !is_poisoned 
				  && data.get_total_combat_value( side ) 
				     < 3.0 * data.get_total_combat_value( !side );

	// Generate at least one action per enemy creature
	for (creature_iterator = battlefield.creatures_begin(); 
	     creature_iterator != battlefield.creatures_end(); ++creature_iterator )
	{
		t_combat_creature_ptr	target = *creature_iterator;

		// Don't attack our units, even if they are hypnotized
		if (target->belongs_to_defender() == side)
			continue;

		if (target.get() == &attacker)
			continue;

		if (target->get_number() == 0)
			continue;

		if (attacker.check_cowardice( *target ))
			continue;
		
		if (target->is_active( k_spell_sanctuary ))
			continue;

		action = generate_melee_action( target, combat_ai, stay_in_castle );
		if (action == 0)
			continue;

		if (best_action == 0 || less_than( *best_action, *action, combat_ai ))
			best_action = action;
	}
	return best_action;
}


